package com.zklh.leetcode.top100;

import java.util.HashMap;
import java.util.Map;

/**
 * 完全平方数算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/11
 */
public class Solution279 {


    public int numSquares(int n) {
        Map<Integer, Integer> numToSquares = new HashMap<>();
        int step = 0;
        while (step * step <= n){
            numToSquares.put(step*step,1);
            step++;
        }
        return numSquares(n, numToSquares);
    }

    public int numSquares(int n, Map<Integer, Integer> numToSquares) {
        if (numToSquares.containsKey(n)) {
            return numToSquares.get(n);
        }
        int step = (int) Math.sqrt(n);
        int min = Integer.MAX_VALUE;
        while (step > 0) {
            int nextSquares = numSquares(n - step * step, numToSquares);
            if (nextSquares == 1) {
                min = 2;
                break;
            }
            min = Integer.min(min, numSquares(n - step * step) + 1);
            step--;
        }
        numToSquares.put(n, min);
        return min;
    }

    public static void main(String[] args) {
        Solution279 solution279  = new Solution279();
        System.out.println(solution279.numSquares(65));
        System.out.println(solution279.numSquares(13));
        System.out.println(solution279.numSquares(35));
    }
}